/*************************************************
* Copyright(c) free                              *
* Beijing Jiaotong University                    *
* AUTHOR: Li Yi,Li Xuewen			 *				
* TEAM: Wasabi                                   *
* This file is use to create the data structure  *
* of TrieTree, its used to store the dictionary. *
* Version 1.0 2011-01-06                         *
*************************************************/
#include <stdio.h>
#include <string.h>
#include <locale.h>
#include <wchar.h>
#include <math.h>
#include <iconv.h>
#include "../include/TrieTree.h"
#include <stdlib.h>

/***************************************************************************************************
 treehash : establish the hash structure. 
 parameter : TrieNode *p
	     a TrieNode pointer to establish the TrieTree structure.
             wchar_t* value
             the inserted word. 
 return type : int 
        value :  the right position in the hash structure. 
 detail descrpition : this function is to return the right position in the hash structure.             
****************************************************************************************************/
inline int treehash(TrieNode *p, wchar_t* value){
    return (unsigned int)value[0] % p->size;
}


/***************************************************************************************************
 hashfactor : establish the hash structure. 
 parameter : int x
	     the position in the hash structure.
 return type : int 
        value :  the least prime number. 
 detail descrpition : this function is to create a hash array size, accord to son number.
 and then return the least prime number which is larger then 2 times son number,
 for example: if a node has 5 son, 11 is the least prime larger then 2*5.             
****************************************************************************************************/
inline int hashfactor(int x){
    if(x<3)//at least 3
    return 3;
    int i,res;
    for(res=x/2*4+1; ; res+=2){
    for(i=3; i<=sqrt(res); i+=2){//is prime
        if(res%i==0)
            break;
    }
    if(res%i!=0)
        return res;
    }
}

/***************************************************************************************************
 initTrieNode : init the TrieNode. 
 parameter : pTrieNode pInitnode
	     a TrieNode pointer
             wchar_t *v
             init the TrieNode's value
 return type : NULL 
 detail descrpition : this function is to init the TrieNode,and the TrieNode's value is v.             
****************************************************************************************************/
void initTrieNode(pTrieNode pInitnode, wchar_t* v){
    pInitnode->sons=NULL;
    pInitnode->first=pInitnode->next=NULL;
    pInitnode->used=0;
    pInitnode->size=0;
    pInitnode->value = ( wchar_t* )malloc( 2 * sizeof( wchar_t ) );
    memset( pInitnode->value, 0, 2 * sizeof( wchar_t ) );
    wcsncpy( pInitnode->value, v, 1 );
    pInitnode->pinyin=NULL;
}

/***************************************************************************************************
 indexadd : add the new TrieNode into the Double Linklist. 
 parameter : pTrieNode root
             the root of the Double LinkList.
	     wchar_t *word
             the new TrieNode's value.
             wchar_t *pinyin
             the new TrieNode's pinyin.
 return type : null. 
 detail descrpition : this function is init the new TrieNode first,and then judge the root,if it is
 null ,then add;otherwise,judge the root->next->value to decide add or repeat to choose the position.             
****************************************************************************************************/
void indexadd(pTrieNode root, wchar_t *word, wchar_t *pinyin){
    TrieNode *prev, *p, *cur = root;
    int nLength;
    for(; *word; word++){
        if(cur->first == NULL){
	    pTrieNode pTmp = malloc(sizeof(TrieNode));
            initTrieNode(pTmp,word);
	    cur->first = pTmp;
            cur->used++;
            cur = cur->first;
            continue;
        }//if it doesn't have a child, make one
        for(p = cur->first; p; prev=p,p=p->next){
            if( wcsncmp( p->value, word, 1 ) == 0 ){
                cur = p;
                break;
            }//if
        }//for
        if(p==NULL){
            pTrieNode pTmp=malloc(sizeof(TrieNode));
            initTrieNode(pTmp,word);
            prev->next = pTmp;
            cur->used++;
            cur = prev->next;
        }//if
    }//for
    nLength = wcslen( pinyin );
    cur->pinyin = ( wchar_t* )malloc( ( nLength + 1 ) * sizeof( wchar_t ) );
    memset( cur->pinyin, 0, ( nLength + 1 ) * sizeof( wchar_t ) );
    wcsncpy( cur->pinyin, pinyin, nLength );
}

/***************************************************************************************************
 indexaddfirstlayer : to establish the first layer of the TrieTree dictionary. 
 parameter : pTrieNode root
             the root of the TrieTree.
	     wchar_t *word
             the value of the new TrieNode's value.
             wchar_t *pinyin
             the value of the new TrieNode's pinyin.
             TrieNode **ppFirstNode
             the pointer of the new TrieNode's sons.
 return type : null.
 detail descrpition : this function is how to read the dictionary fast, so we need to establish the 
 first layer of the TrieTree dictionary,the first layer is fixed.after it,we can build another 
 efficent way to create our TrieTree dictionary.             
****************************************************************************************************/
void indexaddfirstlayer(pTrieNode root, wchar_t *word, wchar_t *pinyin, TrieNode **ppFirstNode ){
    pTrieNode pTmp = malloc(sizeof(TrieNode));
    initTrieNode(pTmp,word);
    int nLength = wcslen( pinyin );
    pTmp->pinyin = ( wchar_t* )malloc( ( nLength + 1 ) * sizeof( wchar_t ) );
    memset( pTmp->pinyin, 0, ( nLength + 1 ) * sizeof( wchar_t ) );
    wcscpy( pTmp->pinyin, pinyin );
    if( *ppFirstNode == NULL ){
	root->first = pTmp;
        *ppFirstNode = pTmp;
        root->used++;
    }
    else{
	(*ppFirstNode)->next = pTmp;
	*ppFirstNode = pTmp;
	root->used++;
    }
}

/***************************************************************************************************
 indexaddotherlayer : to establish the other layer of the TrieTree dictionary. 
 parameter : pTrieNode root
             the root of the TrieTree.
	     wchar_t *word
             the value of the new TrieNode's value.
             wchar_t *pinyin
             the value of the new TrieNode's pinyin.
             TrieNode **ppFirstNode
             the pointer of the new TrieNode's sons.
 return type : null.
 detail descrpition : this function is how to read the dictionary fast, after we build the first  
 layer of the TrieTree dictionary,now we need to establish the other layer.In this process, we need
 to establish the TrieNode's sons,it is a hash structure.             
****************************************************************************************************/
void indexaddotherlayer(pTrieNode root, wchar_t *word, wchar_t *pinyin, TrieNode** ppFirstNode){
    TrieNode *prev, *p, *cur = root;
    int nLength;
    int i;
    int key;

    for( i = 0; *word; word++,i++){
  	if( i == 0 ){
	    key=treehash(cur, word);		
	    for(p=cur->sons[key]; p; p=cur->sons[(++key)%cur->size]){
        	if( wcsncmp( p->value, word, 1 ) == 0 ){
        	    cur = p;
        	    break;
		}
	    }
	    if( p == NULL ){
		pTrieNode pTmp = malloc(sizeof(TrieNode));
        	initTrieNode(pTmp,word);
		(*ppFirstNode)->next = pTmp;
		*ppFirstNode = pTmp;
		root->used++;
		cur = pTmp;
		return;		
	    }
	    continue;
        }	
	if(cur->first == NULL){
	    pTrieNode pTmp = malloc(sizeof(TrieNode));
            initTrieNode(pTmp,word);
	    cur->first = pTmp;
            cur->used++;
            cur = cur->first;
            continue;
    	}//if it doesn't have a child, make one
    	for(p = cur->first; p; prev=p,p=p->next){
            if( wcsncmp( p->value, word, 1 ) == 0 ){
        	cur = p;
        	break;
            }
    	}
    	if(p==NULL){
            pTrieNode pTmp=malloc(sizeof(TrieNode));
            initTrieNode(pTmp,word);
            prev->next = pTmp;
            cur->used++;
            cur = prev->next;
    	}
    }
    nLength = wcslen( pinyin );
    cur->pinyin = ( wchar_t* )malloc( ( nLength + 1 ) * sizeof( wchar_t ) );
    memset( cur->pinyin, 0, ( nLength + 1 ) * sizeof( wchar_t ) );
    wcscpy( cur->pinyin, pinyin );
}

/***************************************************************************************************
 index2tree : to change the Double LinkList into a TrieTree dictionary. 
 parameter : TrieNode *cur
	     the root of the Double LinkList.
 return type : null.
 detail descrpition : this function is to change the double LinkList into a TrieTree dictionary.It
 needs the value of theTrieNode's size and sons. And this is a recursive programe.
****************************************************************************************************/
void index2tree(TrieNode *cur){
    TrieNode *p,*pos;
    int key;
    if( cur==NULL || cur->used == 0 )
        return ;
    cur->size = hashfactor(cur->used);
    TrieNode **pTmp= ( TrieNode **)malloc( sizeof( TrieNode* ) * cur->size);
    cur->sons=pTmp;
    memset((void*)cur->sons, 0, sizeof(TrieNode *)*cur->size);
    for(p = cur->first; p; p=p->next){
    	key=treehash(cur, p->value);
    	for(pos=cur->sons[key]; pos!=NULL; )
            pos=cur->sons[(++key)%cur->size];
    	cur->sons[key%cur->size]=p;
    	index2tree(p);
    }
}

/***************************************************************************************************
 treefind : search the word in the TrieTree dictionary. 
 parameter : TrieNode *root
             the root of the TrieTree dictionary.
	     wchar_t *word
             the search word.
 return type : wchar_t *
        value :  the word's pinyin when successful
                null when failed. 
 detail descrpition : this function is to search the word in the TrieTree dictionary.It repeat the 
 word's every wchar_t unit to compare with the TrieTree dictionary at the same step.So we can know
 the result of the search.             
****************************************************************************************************/
wchar_t * treefind(TrieNode *root, wchar_t *word){
    TrieNode *p, *cur = root;
    for(; *word; word++){
        if( cur->used != 0 ){
    	    int key=treehash(cur, word);
    	    for(p=cur->sons[key]; p; p=cur->sons[(++key)%cur->size]){
        	if( wcsncmp( p->value, word, 1 ) == 0 ){
        	    cur = p;
        	    break;
        	}
    	    }
    	    if(p==NULL)
        	break;
	}
	else {
	    p = NULL;
	    break;
	}	
    }
    if(p==NULL){
        return NULL;}
    else{
        return cur->pinyin; }
}
